#ifndef UnstuctMG_QSORT_HPP
#define UnstuctMG_QSORT_HPP

template<typename idx_t, typename T>
void my_swap(T *v,
            idx_t  i,
            idx_t  j )
{
   T temp;

   temp = v[i];
   v[i] = v[j];
   v[j] = temp;
}

template<typename idx_t, typename T>
void my_qsort0( T *v,
                   idx_t  left,
                   idx_t  right )
{
   idx_t i, last;

   if (left >= right)
   {
      return;
   }
   my_swap(v, left, (left + right) / 2);
   // 选取原序列中点的元素作为pivot
   last = left;// last最后会指向pivot应该放置的位置
   for (i = left + 1; i <= right; i++)
   {
      if (v[i] < v[left])// 把小于pivot的元素都放到前半部分去，放入的位置由last指向
      {
         my_swap(v, ++last, i);// 此时++last所指向的元素如果不是v[i]本身，那么一定比pivot大
      }
   }
   my_swap(v, left, last);// 最后将pivot放置于合适的位置
   my_qsort0(v, left, last - 1);
   my_qsort0(v, last + 1, right);
}

template<typename idx_t, typename key_t, typename val_t, int order>
void my_qsort1( key_t *v, val_t *aux,
               idx_t  left,
               idx_t  right )
{
   static_assert(order == 1 || order == -1);// 1: 升序，-1：降序
   idx_t i, last;

   if (left >= right)
   {
      return;
   }
   my_swap(v  , left, (left + right) / 2);
   my_swap(aux, left, (left + right) / 2);
   // 选取原序列中点的元素作为pivot
   last = left;// last最后会指向pivot应该放置的位置
   for (i = left + 1; i <= right; i++)
   {
      bool need_swap = false;
      if constexpr (order == 1)  need_swap = v[i] < v[left];
      else                       need_swap = v[i] > v[left];
      if (need_swap)// 把小于pivot的元素都放到前半部分去，放入的位置由last指向
      {
         my_swap(v  , ++last, i);// 此时++last所指向的元素如果不是v[i]本身，那么一定比pivot大
         my_swap(aux,   last, i);
      }
   }
   my_swap(v  , left, last);// 最后将pivot放置于合适的位置
   my_swap(aux, left, last);
   my_qsort1<idx_t, key_t, val_t, order>(v, aux, left    , last - 1);
   my_qsort1<idx_t, key_t, val_t, order>(v, aux, last + 1, right   );
}


#endif